package main

func mapContains(m1, m2 map[byte]int) bool {
	if len(m1) < len(m2) {
		return false
	}
	for k, v2 := range m2 {
		if v2 > m1[k] {
			return false
		}
	}
	return true
}

func minWindow(s string, t string) string {
	tm := make(map[byte]int)
	for i := range t {
		c := t[i]
		tm[c]++
	}
	left := 0
	result := ""
	sm := make(map[byte]int)
	for right := range s {
		c := s[right]
		sm[c]++
		for mapContains(sm, tm) {
			if result == "" || right - left + 1 < len(result) {
				result = s[left:right+1]
			}
			c := s[left]
			sm[c]--
			left++
		}
	}
	return result
}